1. Field of the Invention
The invention relates to a variable length coding and decoding method for motion vectors used in connection with a highly efficient technique for coding moving picture data utilizing inter-frame correlation, and more particularly is directed to variable length coding and decoding motion vectors formed with respect to a variety of motion vector ranges and degrees of accuracy.
2. Description of Related Art
When a moving picture signal is digitized for recording or transmission it is often necessary to compress the large amount of data that results from digitization, and for this purpose it is known to perform highly efficient coding of the digitized picture signal.
Recently the International Organization for Standardization has developed a video compression standard for use in video storage applications such as CD-ROM. This proposed standard is described in the document, "Coding of Moving Pictures and Associated Audio", ISO-ISC JTC1/SC2/WG11, MPEG 90/176 Rev. 2; Dec. 18, 1990.
Inter-frame predictive coding using correlation between frames is one known technique for highly efficient coding of a moving picture signal. In particular, inter-frame predictive coding with motion compensation is known, as in the MPEG document referred to above.
Motion compensated predictive coding uses correlation over time within the picture signal. A difference signal is formed for a present frame with respect to a past frame, after compensating for motion in the picture between the two frames.
This technique is described in U.S. Pat. No. 5,132,792, which has common inventors and a common assignee with the present application. The basic theory of motion compensated predictive coding, although well known to those skilled in the art, will now be summarized with reference to FIGS. 1A and 1B. In FIG. 1A, a screen display is shown in which a circular object is displayed. It will be noted that the screen display of FIG. 1A has been divided into blocks. FIG. 1B illustrates the next frame of the moving picture, in which the circular object has moved upwardly and to the right in the screen display.
The center block of FIG. 1A corresponds to the portion indicated by dotted lines in FIG. 1B. Thus the motion of the center block of FIG. 1A between the respective frames of FIGS. 1A and 1B is represented by a vector known as a "motion vector" and represented, in turn, by the arrow which appears in FIG. 1B.
In an apparatus for performing inter-frame predictive coding with motion compensation, a predictive reference picture is formed by locally decoding a picture for a previous frame and then moving the picture in accordance with a motion vector which represents motion between the previous frame and the frame which is presently to be coded. An inter-frame difference signal, between the present frame and the predictive reference picture is formed in order to provide a predictive error signal. The predictive error signal and the motion vector used to form the predictive reference picture are then output by the coding apparatus. At the decoding apparatus the present frame can be decoded on the basis of the picture data for the previous frame, the motion vector, and the predictive error signal. In this way, utilizing motion compensation, the total amount of data to be stored or transmitted can be reduced.
FIG. 1C illustrates an example of motion compensated predictive coding. In this example, each picture (a frame or a field) is divided into a large number of two dimensional blocks. For example, each block may be 16.times.16 picture elements. The motion compensated predictive coding is performed on a block by block basis. The motion vector is made up of X and Y components which respectively represent motion in the horizontal and vertical directions. According to a commonly used convention, motion in a rightward or downward direction is assigned a positive value and motion in a leftward or upward direction is assigned a negative value.
As shown in FIG. 1C, a sequence of moving pictures n+1, n+2 and n+3 follow a reference picture n and are respectively assigned motion vectors V1, V2 and V3.
When there is a strong correlation among the pictures and an object moves in a straight path at a substantially constant speed, the following relations apply: EQU V2=2.times.V1 (1) EQU V3=3.times.V1 (2)
These relations can be generalized as follows with respect to the magnitude of a motion vector for pictures having a strong correlation: EQU Vk=k.times.V1 (3)
FIG. 2 illustrates in graphical form the probability .phi. of occurrence of each value "a" of each element X or Y of a motion vector (X, Y). The probability function .phi. V1 (a) of the values for the motion vector V1 in relation to the probability function .phi. Vk (a) of the values of the motion vector Vk (obtained by multiplying V1 by k) is shown in FIG. 2 with .phi. Vk (a) being formed by horizontally multiplexing .phi. V1 (a) by k (because of expression (3)). (When these probability functions are totally integrated, the resulting value is one.) Thus, .phi. V1 (a) is obtained by dividing .phi. Vk (a) by k. Accordingly, when the (k times) motion vector Vk is divided by the distance between frames k, the same probability distribution is obtained as for the motion vector V1. In other words, the 1-frame-displacement motion vector V1, after multiplication by k, may be used as the k-frames-displaced motion vector Vk.
The values of the elements X and Y of the motion vector (X, Y) are each variable-length coded using Huffman code or the like prior to transmission. A variable length coding table is used to optimize the allocation of code length in accordance with the statistical distribution of the values of X and Y. For values of X and Y that occur frequently, a short coding length is assigned. On the other hand, for values having a low frequency of occurrence, a long coding length is assigned.
In U.S. Pat. No. 5,132,792, referred to above, optimization of a variable length code (VLC) table and a basic theory for sharing the table have been proposed.
The range and degree of accuracy for a motion vector can be arbitrarily assigned. For example, the range of a motion vector can be assigned as .+-.7 or .+-.15 picture elements with respect to the origin. In other words, the value of the motion vector can be selected from among -7, -6, . . . , 0, . . . , +6, +7, or -15, -14, . . . , 0, . . . , +14, +15 in the respective cases. The degree of accuracy for a motion vector can be assigned as, for example, one picture element or 0.5 picture element (half pel).
Consideration will next be given to motion vectors formed with respect to a plurality of ranges and degrees of accuracy.
According to prior art coding techniques, respective VLC tables were required for coding motion vectors formed with respect to a first range of, for example, .+-.7 picture elements and motion vectors formed with respect to a range of .+-.15 picture elements. For the .+-.7 picture element range, and where a degree of accuracy of one picture element is to be provided, the corresponding VLC table has 15 entries corresponding to -7, -6, . . . , 0, . . . , +6, +7. On the other hand, a second VLC table for the range of .+-.15 picture elements, with an accuracy of one picture element, has 31 entries corresponding to -15, -14, . . . , 0, . . . , +14, +15. Moreover, if it is also desired to form motion vectors over the .+-.7 picture element range but with a degree of accuracy of 0.5 picture elements, then the corresponding VLC table has 29 entries, corresponding to -7.0, -6.5, -6.0, . . . , 0, . . . +6.0, +6.5, +7.0.
According to prior art techniques, when there were several desired ranges and degrees of accuracy for motion vectors, the required number of VLC tables increased. This resulted in an increased need for memory storage capacity, which also increased the scale of the hardware.
A possible solution to this problem is to provide a VLC table for the largest desired range and finest desired degree of accuracy and then to share the same table for the respective motion vectors formed with respect to the various ranges and degrees of accuracy. For example, a VLC table for the .+-.15 picture element range may be provided and used for a motion vector formed with respect to a .+-.7 picture element range. However, in this case redundant codes are used so that the coding efficiency is reduced. This is because a VLC code which is optimized for coding efficiency over a range of .+-.15 picture elements is different from a VLC table optimized for coding over a range of .+-.7 picture elements.